Magnetic recording systems are commonly used for secondary storage in computer systems. As a result of the widespread use of, and growing applications for computers, there is a continuous demand for increased storage capacity. Therefore, methods and apparatus for increasing recording densities, the amount of information stored in a given volume, are continuously explored.
As recording density increases, the electronic pulses induced on the read heads by adjacent bits increasingly tend to interfere and partially cancel each other, resulting in a decrease of the intensity of the detected signal. In addition, the noise increases as a result of various effects, such as the interference from nearby tracks. The net result is that the signal to noise ratio ("SNR") tends to decrease rapidly with increased recording density. Accordingly, with increased densities, there is also a need for more advanced signal processing techniques.
One of the signal processing techniques that has resulted in significant increases in density is known as "Partial Response Maximum Likelihood" (PRML). This technique was introduced in H. Kobayashi and D. T. Tang, Application of Partial-Response Channel Coding to Magnetic Recording Systems, 14 IBM Journal of Research and Development pp. 368-375 (July 1970), hereby incorporated by reference as if fully set forth herein, but not applied to disk drive systems until very recently. In this technique, the discrete-time channel response is shaped by means of an adaptive filter called an Equalizer, in such a way that its transfer function, expressed as a D-transform, is EQU H(D)=1-D.sup.2 ( 1)
This response is usually known as "Partial Response Class IV" (PR IV), and was first described in A. Lender, Correlative Level Coding for Binary Data Transmission, 3 IEEE Spectrum pp. 106-115 (February 1966), and E. R. Kretzmer, Generalization of a Technique for Binary Data Communication, COM-14 IEEE Transactions on Communications pp. 67-68 (February 1966), and further developed by P. Kabal and S. Pasupathy, Partial-Response Signalling, COM-23 IEEE Transactions on Communications (September 1975), all three of which are hereby incorporated by reference as if fully set forth herein.
PRML is the result of combining PR IV with another technique called "Maximum Likelihood Detection", introduced in A. J. Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IT-13 IEEE Transactions on Information Theory pp. 260-269 (April 1967), and further developed in G. D. Forney, Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference, IT-18 IEEE Transactions on Information Theory (May 1972), and G. D. Forney, The Viterbi Algorithm, 61 Proceedings of the IEEE pp. 268-278 (March 1973), all three of which are hereby incorporated by reference, as if fully set forth herein. Other types of partial responses of interest in magnetic recording channels are described in H. K. Thapar and A. M. Patel, A Class of Partial Response Systems for Increasing Storage Density in Magnetic Recording, MAG-23 IEEE Transaction on Magnetics pp. 3666-3668 (September 1987), hereby incorporated by reference as if fully set forth herein. These responses are of the general type EQU H(D)=(1-D)(1+D).sup.n ( 2)
The case of PR IV mentioned above is a special case of this equation, for which n=1. Another case of interest in the context of the present invention is the case of n=2, a response known as "Extended Partial Response Class IV", or EPR IV.
A maximum likelihood sequence detection ("MLSD") scheme determines the sequence of data symbols that best matches an observed sequence of signal samples that have been corrupted by noise and interference. A common implementation of an MLSD scheme involves the Viterbi algorithm. The Viterbi algorithm performs maximum likelihood sequence detection of finite state signals in noise.
In many situations, the state space is too large to search directly. One example of such a situation is when the channel response extends over a long time. In general, if the number of nonzero samples of the channel impulse response is L, the number of states required for an optimal Viterbi decoder for binary data is 2.sup.(L-1). Thus the complexity of the optimal decoder grows exponentially with the length of the channel impulse response. In these situations, suboptimal detection techniques may provide a reasonable tradeoff between performance and complexity.
Concatenated decoding schemes are an example of suboptimal detection schemes whose performance often approaches the performance of the optimal decoder and whose complexity is substantially lower. One exemplary concatenated decoding scheme is found in N. Seshadri and C. E. W. Sunberg, Generalized Viterbi Algorithms for Error Detection with Convolutional Codes, Proceedings of Globecom 89, pp. 1534-1538, hereby incorporated by reference as if fully set forth herein. This scheme as well as others of its kind, include a modified Viterbi algorithm in which an ordered list of an arbitrary number ("N") of best paths and their corresponding likelihoods, each corresponding to a sequence of data which may reflect the transmitted sequence of data, are produced while an error detection code chooses the first error-free path from the list.
An alternative to an N-best Viterbi algorithm is to generate a list of candidate data sequences by adding minimum-distance error events to the single best path released by the Viterbi decoder. This scheme was used in decoding DC-free block codes in partial response channels in K. Knudson, et al., A Concatenated Decoding Scheme for (1-D) Partial Response with Matched Spectral Null Coding, Proceedings of GLOBECOM 93, hereby incorporated by reference as if fully set forth herein. The inner decoder ignores the code constraints, while a postprocessor eliminates the sequences that violate the constraints.
As mentioned, increased storage density tends to increase the amount of interference between adjacent bits and tracks. The interference among adjacent bits is referred to as intersymbol interference ("ISI"), and the interference between adjacent tracks is called intertrack interference ("ITI"). Specifically, ISI occurs because the detected pulses are not properly confined to their time slot, i.e., baud period, available to the reading of a single data symbol. As a result, the neighboring pulses interfere with each other and degrade the margin against random noise available to the detector.
Owing to the importance of storage capacity of magnetic recording systems, various methods have been proposed for compensating ISI. The most common of such methods is equalization, which is well known to those skilled in the art. Another method using tentative decisions is described in O. E. Agazzi and N. Seshadri, Cancellation of Precursor Intersymbol Interference in Magnetic Recording Channels, U.S. patent application Ser. No. 08/381,630, filed on Jan. 31, 1995, hereby incorporated by reference as if fully set forth herein.
Intersymbol interference is, however, only one of the many impairments that limit the storage density. Other impairments include intertrack interference, as mentioned above, and nonlinear distortion. Nonlinearity arises in the magnetic recording channel as a result of factors such as the hysteresis of the magnetic material. It may also arise as a result of the nonlinear transfer characteristic of certain heads, known as magnetoresistive heads.
Nonlinear distortion can be considered a generalized intersymbol interference. A more complete description of nonlinear distortion in data transmission systems is discussed in O. E. Agazzi et al., Nonlinear Echo Cancellation of Data Signals, COM-30 IEEE Transactions on Communications pp. 2421-2433 (November 1982) and in O. E. Agazzi et al., Timing Recovery in Digital Subscriber Loops, COM-33 IEEE Transactions on Communications pp. 558-569 (June 1985), both of which are hereby incorporated by reference as if fully set forth herein. Another description is given in R. Hermann, Volterra Modeling of Digital Magnetic Saturation Recording Channels 26 IEEE Transactions on Magnetics pp. 2125-2127, App. A (September 1990), hereby incorporated by reference as if fully set forth herein. These descriptions can also be applied to nonlinear distortion in magnetic recording channels.
Write precompensation techniques are known in the prior art and are useful for compensating part of the nonlinearity in magnetic recording channels. However, write precompensation is not perfect, and substantial nonlinearity remains in the precompensated signals. This motivates the use of other techniques to alleviate the detrimental effects of nonlinearity.
One possible technique would be cancellation as, for example, based on tentative decisions, as is used for linear intersymbol interference and described in the above referenced U.S. Patent Application. However, it has been shown that cancellation is not effective for the case of nonlinearity. The reasons for this lack of effectiveness are explained in O. E. Agazzi and N. Seshadri, When Can Tentative Decisions be Used to Cancel (Linear or Nonlinear) Intersymbol Interference? (With Application to Magnetic Recording Channels), Proceedings of the 1995 International Conference on Communications pp. 647-652 (Seattle, Washington, June 1995), hereby incorporated by reference as if fully set forth herein.
Another possible technique to mitigate the effects of nonlinearity in magnetic recording channels is to implement the Viterbi algorithm to perform a maximum likelihood sequence detection based on a model of the channel that incorporates a complete description of the nonlinearity. In this technique, the branch metric associated with the transition between two arbitrary states S.sub.n-1 and S.sub.n is given by (y.sub.n -F(a.sub.n, a.sub.n-1, . . . , a.sub.n-M+1)).sup.2 where y.sub.n is the most recent sample of the received signal, a.sub.n, a.sub.n-1, . . . , a.sub.n-M+1 are the M bits associated with the transition between states S.sub.n-1 and S.sub.n, and F() is a nonlinear function that models the channel. This nonlinear function is usually not known a priori, but it can be estimated using nonlinear adaptive filtering techniques well known in the prior art. See, e.g. O. E. Agazzi et al., Nonlinear Echo Cancellation of Data Signals, supra and N. Holte and S. Stueflotten, A New Digital Echo Canceler for Two-Wire Subscriber Lines, COM-29 IEEE Transactions on Communications (November 1981), hereby incorporated by reference as if full set forth herein.
Although in principle this method provides the optimal performance, a major problem is its complexity. As was mentioned before, the complexity of the Viterbi decoder grows exponentially with the length of the channel response. This applies both to the linear and the nonlinear case.
A related problem is that often a significant portion of the nonlinear components of the channel response appear as "precursors," components that precede in time, the appearance of the main component of the channel response. These precursors can, in principle, be taken into account by a nonlinear channel estimator in the Viterbi decoder. However each additional precursor that is accounted for results in doubling the number of states.
Another related problem is that the Viterbi decoder is optimal only if the noise at its input is white. This is usually accomplished by using a whitened matched filter at the input stage of the receiver, as described in G. D. Forney, Maximum-Likelihood Sequence Estimation of Digital Sequences in the Presence of Intersymbol Interference, supra. However the use of a whitened matched filter often results in exceedingly long channel responses and requires a Viterbi decoder with an impracticable number of states. In application, this problem is usually circumvented by not using a whitened matched filter at the input stage of the receiver. However, this results in substantial loss of performance. The problem of the exponential growth of the complexity of the Viterbi decoder is exacerbated even more when a channel code is used, and it is desired to perform joint decoding of the channel and the code.
A primary motivation for the present invention is that, in order to keep the complexity of the Viterbi decoder within reasonable bounds, it is necessary to limit the number of its states. As a result, the Viterbi decoder often operates under "mismatched conditions," which means that it uses a simplified model of the channel that ignores the components of the channel response which result in linear and nonlinear intersymbol interference, and it ignores noise correlation. The resulting increase in the error rate is compensated through postprocessing techniques aimed at correcting a large fraction of the errors that arise from the mismatch.